﻿#define _CRT_SECURE_NO_WARNINGS 1

//1005. K 次取反后最大化的数组和
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {

        int m = 0, minElem = INT_MAX, n = nums.size();
        for (auto x : nums)
        {
            if (x < 0) ++m;
            minElem = min(minElem, abs(x));// 求绝对值最⼩的那个数
        }

        // 分类讨论
        int ret = 0;
        if (m > k)
        {
            sort(nums.begin(), nums.end());
            for (int i = 0; i < k; ++i)// 前 k ⼩个负数，变成正数
                ret += abs(nums[i]);
            for (int i = k; i < n; ++i)// 后⾯的数不变
                ret += nums[i];
        }
        else
        {
            // 把所有的负数变成正数
            for (auto x : nums) ret += abs(x);
            if ((k - m) % 2)// 判断是否处理最⼩的正数
            {
                ret -= minElem * 2;
            }
        }
        return ret;
    }
};